package Top_Interview_Questions.Hash_Table;



import Top_Interview_Questions.Hash_Table.Supple.Node;

import java.util.HashMap;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/10 12:19
 * <p>
 * 功能描述:
 */
public class _0138 {

    public static void main(String[] args) {
        _0138 test = new _0138();

         Node node1 = new Node(4);
         Node node2 = new Node(7);
         Node node3 = new Node(-2);

         node1.next = node2;
         node2.next = node3;

         node1.random = node3;
         node2.random = node1;

        Node clone = test.copyRandomList(node1);
        System.out.println(clone);
    }


    /*----------------------------------O(N)空间的迭代--------------------------------------------*/

    // Visited dictionary to hold old node reference as "key" and new node reference as the "value"
    HashMap<Node, Node> visited = new HashMap<Node, Node>();

    /**
     * 还有一个O(1)空间的迭代,只看了思想,代码没看。
     */
    public Node copyRandomList(Node head) {

        if (head == null) {
            return null;
        }

        Node oldNode = head;

        // Creating the new head node.
        Node newNode = new Node(oldNode.val);
        this.visited.put(oldNode, newNode);

        // Iterate on the linked list until all nodes are cloned.
        while (oldNode != null) {
            // Get the clones of the nodes referenced by random and next pointers.
            newNode.random = this.getClonedNode(oldNode.random);
            newNode.next = this.getClonedNode(oldNode.next);

            // Move one step ahead in the linked list.
            oldNode = oldNode.next;
            newNode = newNode.next;
        }
        return this.visited.get(head);
    }

    public Node getClonedNode(Node node) {
        // If the node exists then
        if (node != null) {
            // Check if the node is in the visited dictionary
            if (this.visited.containsKey(node)) {
                // If its in the visited dictionary then return the new node reference from the dictionary
                return this.visited.get(node);
            } else {
                // Otherwise create a new node, add to the dictionary and return it
                this.visited.put(node, new Node(node.val));
                return this.visited.get(node);
            }
        }
        return null;
    }


    /*---------------------------------------------------------------------------------------*/
}
